package main.kotlin

/**
 * @since 2018.5.26
 * @version 0.1
 * @author 张一鸣
 * 二叉树
 */
import java.util.*

class BST<Key : Comparable<Key>, Value> {
    private var root: Node? = null

    inner class Node(val key: Key, var value: Value, var N: Int) {
        var left: Node? = null
        var right: Node? = null
    }

    /**
     * 返回二叉树的大小
     * @param x Node，默认是整个树的大小，可以查询部分树的大小
     * @return int
     */
    fun size(x: Node?=this.root): Int {
        return x?.N ?: 0
    }

    /**
     * 根据键值，返回树上特定的值
     * @param key Key,键值
     * @return value或者null
     */
    fun getValue(key: Key): Value? {
        return get(this.root, key)
    }

    /**
     * 递归查找键值
     * @param x Node，二叉树
     * @param key Key，键值
     * @return value或者null
     */
    private fun get(x: Node?, key: Key): Value? {
        if (x == null) return null
        val cmp = key.compareTo(x.key)
        var result: Value? = x.value
        when {
            cmp < 0  -> result = get(x.left, key)
            cmp > 0 -> result = get(x.right, key)
        }
        return result
    }

    /**
     * 向二叉树中添加数据
     * @param key Key，键值
     * @param value Value，值
     * @return
     */
    fun put(key: Key, value: Value) {
        this.root = this.put(this.root, key, value)
    }

    /**
     * 按照kotlin的语法，这一段添加在上边的function里也可以
     * 此处将其单独写出来，主要是为了put函数的密封性，以免用户通过此函数改变类内部不应当被改变的变量
     */
    private fun put(x: Node?, key: Key, value: Value): Node {
        if (x == null) return Node(key, value, 1)

        when {
            key < x.key -> x.left = put(x.left, key, value)
            key > x.key -> x.right = put(x.right, key, value)
            key == x.key -> x.value = value
        }
        x.N = this.size(x.left) + this.size(x.right) + 1
        return x
    }

    /**
     * 返回树中最小节点的键值
     */
    fun min(): Key? {
        val result = min(this.root)
        if (result != null) {
            return result.key
        }
        return null
    }

    private fun min(x: Node?): Node? {
        if (x == null) return null
        if (x.left == null) return x
        return this.min(x.left)
    }

    /**
     * 返回树中最大节点的键值
     */
    fun max(): Key? {
        val result = max(this.root)
        if (result != null) {
            return result.key
        }
        return null
    }

    private fun max(x: Node?) : Node? {
        if (x == null) return null
        if (x.right == null) return x
        return this.max(x.right)
    }

    /**
     * 返回树中某节点的向下整数
     */
    fun floor(key: Key): Key? {
        val x: Node = floor(this.root, key) ?: return null
        return x.key
    }

    private fun floor(x: Node?, key: Key): Node? {
        when {
            x == null -> return null
            key == x.key -> return x
            key > x.key -> return this.floor(x.right, key)
            else -> return this.floor(x.left, key) ?: x
        }

    }

    /**
     * 返回某节点的向上整数
     */
    fun ceiling(key: Key): Key? {
        val x: Node = ceiling(this.root, key) ?: return null
        return x.key
    }

    private fun ceiling(x: Node?, key: Key): Node? {
        when {
            x == null -> return null
            key == x.key -> return x
            key > x.key -> return this.ceiling(x.right, key)
            else -> return this.ceiling(x.left, key) ?: x
        }
    }

    /**
     * select找出某排名上的节点
     */
    private fun select(x: Node?, k: Int): Node? {
        if (x == null) return null
        val t = this.size(x.left)

        when {
            t > k -> return select(x.left, k)
            t < k -> return select(x.right, k)
            else -> return x
        }
    }

    fun select(k: Int): Key? {
        return select(this.root, k)?.key
    }

    /**
     * rank 按照键值，返回在该二叉树中的排名（index）
     */
    private fun rank(x: Node?, key: Key): Int {
        when {
            x == null -> return 0
            key < x.key -> return rank(x.left, key)
            key > x.key -> return rank(x.right, key)
            else -> return size(x.left)
        }
    }

    fun rank(key: Key): Int {
        return this.rank(this.root, key)
    }

    /**
     * 删除最小节点
     */
    private fun deleteMin(x: Node?): Node? {
        if (x == null) return null
        when (x.left) {
            null -> return x.right
            else -> {
                x.left = this.deleteMin(x.left)
                x.N = this.size(x.left) + this.size(x.right) + 1
            }
        }
        return x
    }

    fun deleteMin() {
        this.root = this.deleteMin(this.root)
    }

    /**
     * 删除最大节点
     */
    private fun deleteMax(x: Node?): Node? {
        if (x == null) return null
        when (x.right) {
            null -> return x.left
            else -> {
                x.right = this.deleteMax(x.right)
                x.N = this.size(x.left) + this.size(x.right) + 1
            }
        }
        return x
    }

    fun deleteMax() {
        this.root = this.deleteMax(this.root)
    }

    /**
     * 删除指定节点
     */
    private fun delete(x: Node?, key: Key): Node? {
        if (x == null) return null
        var result: Node = x
        when {
            key > x.key -> x.left = this.delete(x.left, key)
            key < x.key -> x.right = this.delete(x.right, key)
            else -> {
                if (x.right == null) return null
                if (x.left == null) return null
                // 此处已经检查过了，左右都还有分支，因此此处不可能为null，有就报错
                val t = x
                // 取出右边树，除开本节点之外的最小节点，然后将左右拼接起来
                result = this.min(t.right)!!
                result.right = this.deleteMin(t.right)
                result.left = t.left
            }
        }
        result.N = this.size(result.left) + this.size(result.right) + 1
        return result
    }

    /**
     * 找出特定范围内的节点，以下为书中的经典算法，java可参考
      */
    private fun keys(x: Node?, low: Key, high: Key): Iterable<Key>? {
        val tmpQueue = ArrayDeque<Key>()
        this.keys(x, low, high, tmpQueue)
        return tmpQueue
    }

    private fun keys(x: Node?, low: Key, high: Key, queue: Queue<Key>) {
        if (x == null) return
        // 这里必须拆成三个判断，如果下方还有，就继续往下走；如果上方还有就继续往上走
        if (low < x.key) this.keys(x.left, low, high, queue)
        if (x.key in low..high) queue.add(x.key)
        if (x.key < high) this.keys(x.right, low, high, queue)
    }

    /**
     * 可以利用kotlin的默认参数特性，将原本的两个private keys()写成一个
     */
    private fun keysByKotlin(x: Node?, low: Key, high: Key, queue: Queue<Key> = ArrayDeque<Key>()): Queue<Key> {
        var tmpQueue = queue
        if (x != null) {
            // 这里必须拆成三个判断，如果下方还有，就继续往下走；如果上方还有就继续往上走
            if (low < x.key) {
                tmpQueue = this.keysByKotlin(x.left, low, high, tmpQueue)
            }
            if (x.key in low..high) tmpQueue.add(x.key)
            if (x.key < high) {
                tmpQueue = this.keysByKotlin(x.right, low, high, queue)
            }
        }
        return tmpQueue
    }

    fun keys(low: Key=this.min()!!, high: Key=this.max()!!): Iterable<Key>? {
        return this.keys(this.root, low, high)
    }
}

fun main(args: Array<String>) {
    val test = BST<Int, Int>()

    for (i in 0..10) {
        test.put(i, i+1)
    }

    println(test.keys(2, 5))
}